class SubrectangleQueries(object):

    def __init__(self, rectangle):
        """
        :type rectangle: List[List[int]]
        """
        self.m = len(rectangle)
        self.n = len(rectangle[0])
        self.p = [[0 for _ in range(4 * self.n)] for _ in range(self.m)]
        for i in range(self.m):
            for j in range(self.n):
                self.update(i, 0, 0, self.n - 1, j, j, rectangle[i][j])

    def update(self, i, node, ls, rs, l, r, value):
        if l <= ls and r >= rs:
            self.p[i][node] = value
        else:
            self.down(i, node)
            mid = (ls + rs) // 2
            if l <= mid:
                self.update(i, 2 * node + 1, ls, mid, l, r, value)
            if r >= mid + 1:
                self.update(i, 2 * node + 2, mid + 1, rs, l, r, value)

    def query(self, i, node, ls, rs, c):
        if c == ls == rs:
            return self.p[i][node]
        else:
            self.down(i, node)
            mid = (ls + rs) // 2
            if mid >= c:
                return self.query(i, 2 * node + 1, ls, mid, c)
            else:
                return self.query(i, 2 * node + 2, mid + 1, rs, c)

    def down(self, i, node):
        if self.p[i][node]:
            self.p[i][2 * node + 1] = self.p[i][node]
            self.p[i][2 * node + 2] = self.p[i][node]
            self.p[i][node] = 0

    def updateSubrectangle(self, row1, col1, row2, col2, newValue):
        for i in range(row1, row2 + 1):
            self.update(i, 0, 0, self.n - 1, col1, col2, newValue)

    def getValue(self, row, col):
        return self.query(row, 0, 0, self.n - 1, col)


obj = SubrectangleQueries([[1, 2, 1], [4, 3, 4], [3, 2, 1], [1, 1, 1]])
obj.updateSubrectangle(0,0,3,2,5)
print(obj.getValue(0,2))
print(obj.p)

